package offer.roratearray;

/**
 * @Author Elephas
 * @Date 2022/1/15
 **/
public class RotateArray1 {
    public static void main(String[] args) {
        final int[] TEST01 = new int[]{4,5,6,7,0,1,2};
        final int[] TEST02 = new int[]{2,2,2,3,2,2,2};
        new RotateArray1().search(TEST02,3);

    }
    /*
        解法一：先找到旋转点o(logn)，对旋转点两侧分别就进行二分搜索。
        写法：先暴力找到旋转点o(n)，然后写出二分搜索。代码ac过后在将寻找旋转点的算法优化为o(logn)
     */

    /**
     * search 当 target 存在数组中时，返回true，否则false
     * @param nums
     * @param target
     * @return
     */

    public boolean search(int[] nums,int target){
        int rotatePoint = findRotatePoint(nums);
        int leftAns = binarySearch(nums,0, rotatePoint-1,target);
        int rightAns = binarySearch(nums, rotatePoint,nums.length-1,target);
        if( leftAns != -1){
            return true;
        }else if(rightAns != -1){
            return true;
        }else{
            return false;
        }
    }
    /**
     * search， 寻找旋转数组中 nums 的 target，如果存在返回下标，不存在返回-1
     */
    /*
    public int search(int nums[], int target){

        int rotatePoint = findRotatePoint(nums);
        int leftAns = binarySearch(nums,0, rotatePoint-1,target);
        int rightAns = binarySearch(nums, rotatePoint,nums.length-1,target);
        if( leftAns != -1){
            return leftAns;
        }else if(rightAns != -1){
            return rightAns;
        }else{
            return -1;
        }
    }


     */
    public int binarySearch(int[] nums,int low,int high,int target){
        int left = low, right = high, mid = -1;
        while(left <= right){
            mid = left + (right - left)/2;
            if(nums[mid] < target ){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else {
                break;
            }
        }
        if( left <= right)
            return mid;
        else
            return -1;
    }

    public static int findRotatePoint(int[] nums){
        int low = 0, high = nums.length-1;
        int mid = 0;
        int pivot = nums[0];
        while( low <= high){
            mid = low + (high - low)/2;
            if(nums[mid] > nums[low]){
                if(nums[mid]>pivot){
                    low = mid + 1;
                }else{
                    high = mid;
                }
            }else if(nums[mid] < nums[high]){
                high = mid;
            }else {
                high --;
            }
        }
        return low;
    }
    public static int forceFindRotatePoint(int[] nums){
        int minIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] < nums[minIndex])
                minIndex = i;
        }
        return minIndex;
    }

    /**
     * 暴力搜索，找到下标
     * @param nums
     * @param target
     * @return
     */
    public int forceSearch(int[] nums, int target){
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target)
                return target;
        }
        return -1;
    }

}
